/*
 *  Librarie de tipuri de date abstracte (TDA)
 
    Copyright (C) 2007  Catedra de Structuri de Date

    This program is free software; you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation; either version 2 of the License, or
    (at your option) any later version.

    This program is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License along
    with this program; if not, write to the Free Software Foundation, Inc.,
    51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 */
 
 
#include <stdlib.h>
#include "linkedstack.h"
#include "binarytree.h"
#include "binarysearchtree.h"

/*
 * Structures
 */

struct _bst_node
{
    struct BT_Node node;
    void *data;
}

struct _bst_adt
{
    struct BT_Tree tree;
    BST_Comparator cmp;
};

/*
 * Private functions
 */

LinkedList _bst_common_find( BinarySearchTree bst, void *data )
{
    LinkedList res = LL_New( );
    struct BT_Node *p = BT_GetRoot( bst );
    for( ; p != BT_NULL ; )
    {
        LL_Add( res, p );

        struct _bst_node *q = (struct _bst_node*)BT_GetKey( p );
        int cres = bst->cmp( data, q->data );
        if( cres == 0 )
            break;

        if( cres < 0 )
            p = BT_GetLSon( p );
        else
            p = BT_GetRSon( p );
    }
    return res;
}

/*
 * Public functions
 */

BinarySearchTree BST_New( BST_Comparator cmp )
{
    struct _bst_adt bst = (struct _bst_adt*)malloc( sizeof( struct _bst_adt ) );
    bst->tree = BT_New( );
    bst->cmp = cmp;
    return bst;
}

void BST_Free( BinarySearchTree bst )
{
    BT_Free( bst->tree );
    free( bst );
}

int BST_Empty( BinarySearchTree bst )
{
    return BT_Empty( bst->tree );
}

int BST_Size( BinarySearchTree bst )
{
    return BT_Size( bst->tree );
}

BSTIterator BST_Find( BinarySearchTree bst, void *data )
{
    LinkedList ln = _bst_common_find( bst, val );
    struct bst_node *p = NULL;

    // get the last element of the list
    if( !LL_Empty( ln ) )
        p = LL_Get( ln, LL_RBegin( ) );
    LL_Free( ln );
    return p;
}

